package algorithm.dynamic_programming;

public class CardsInLine {

    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));
    }

    public static int f(int[] arr, int left, int right) {
        if (left == right)
            return arr[left];
        return Math.max(arr[left] + s(arr, left + 1, right),
                arr[right] + s(arr, left, right - 1)
        );

    }

    public static int s(int[] arr, int left, int right) {
        if (left == right)
            return 0;
        //后手得到的是先手留下的最坏的情况
        return Math.min(f(arr, left + 1, right),
                f(arr, left, right - 1)
        );
    }

    public static int win2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[][] f = new int[arr.length][arr.length];
        int[][] s = new int[arr.length][arr.length];
        for (int i = 0; i < arr.length; i++) {
            f[i][i] = arr[i];
            s[i][i] = 0;
        }
        for (int right = 1; right < arr.length; right++) {
            int temp = right;
            for (int left = 0; left < arr.length - right; left++, temp++) {
                f[left][temp] = Math.max(arr[left] + s[left + 1][temp], arr[temp] + s[left][temp - 1]);
                s[left][temp] = Math.min(f[left + 1][temp], f[left][temp - 1]);
            }
        }
        return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);
    }

    public static void main(String[] args) {
        int[] a = {10, 100, 50, 12};
        int i = win1(a);
        int i1 = win2(a);
        System.out.println(i);
        System.out.println(i1);
    }

}
